#include <stdlib.h>  // 标准库函数，如malloc、atoi等
#include <unistd.h>  // 提供系统调用，如getpid
#include <stdio.h>   // 标准输入输出函数，如printf
#include <assert.h>  // 断言函数，用于调试
#include <pthread.h> // 多线程支持，如pthread_create、pthread_join
#include <sys/time.h> // 时间函数，如gettimeofday
pthread_mutex_t lock;

#define SOL          // 可能用于条件编译（未使用）
#define NBUCKET 5    // 哈希表的桶数量，设为5
#define NKEYS 100000 // 总键值对数量，设为100,000

struct entry {       // 哈希表的节点结构
  int key;           // 键
  int value;         // 值
  struct entry *next; // 指向下一个节点的指针
};
struct entry *table[NBUCKET]; // 哈希表，每个桶是一个链表
int keys[NKEYS];              // 存储所有键的数组
int nthread = 1;              // 线程数量，默认为1
volatile int done;            // 用于同步线程的变量，标记线程是否完成

double now() {                // 获取当前时间的函数
  struct timeval tv;          // 时间结构体
  gettimeofday(&tv, 0);       // 获取当前时间（秒和微秒）
  return tv.tv_sec + tv.tv_usec / 1000000.0; // 返回秒数（精确到微秒）
}

static void print(void) {     // 打印哈希表内容的函数
  int i;                      // 循环变量
  struct entry *e;            // 链表节点指针
  for (i = 0; i < NBUCKET; i++) { // 遍历每个桶
    printf("%d: ", i);         // 打印桶索引
    for (e = table[i]; e != 0; e = e->next) { // 遍历链表
      printf("%d ", e->key);   // 打印键
    }
    printf("\n");             // 换行
  }
}

static void insert(int key, int value, struct entry **p, struct entry *n) {
  struct entry *e = malloc(sizeof(struct entry)); // 分配新节点内存
  e->key = key;               // 设置键
  e->value = value;           // 设置值
  e->next = n;                // 设置下一个节点
  *p = e;                     // 将新节点插入链表
}

static void put(int key, int value) { // 插入键值对的函数
  pthread_mutex_lock(&lock);
  int i = key % NBUCKET;       // 计算桶索引
  insert(key, value, &table[i], table[i]); // 插入到对应桶的链表中
  pthread_mutex_unlock(&lock);
}

static struct entry* get(int key) { // 查找键的函数
  //pthread_mutex_lock(&lock);
  struct entry *e = 0;          // 初始化节点指针
  for (e = table[key % NBUCKET]; e != 0; e = e->next) { // 遍历链表
    if (e->key == key) break;   // 找到键，退出循环
  }
  //pthread_mutex_unlock(&lock);
  return e;                     // 返回找到的节点指针（未找到则返回NULL）
  
}

static void *thread(void *xa) { // 线程函数
  long n = (long) xa;           // 线程编号
  int i;                        // 循环变量
  int b = NKEYS / nthread;      // 每个线程处理的键数量
  int k = 0;                    // 缺失键的计数器
  double t1, t0;                // 时间变量

  t0 = now();                   // 记录插入阶段开始时间
  for (i = 0; i < b; i++) {     // 插入阶段
    put(keys[b * n + i], n);    // 插入键值对
  }
  t1 = now();                   // 记录插入阶段结束时间
  printf("%ld: put time = %f\n", n, t1 - t0); // 打印插入时间

  __sync_fetch_and_add(&done, 1); // 原子操作，增加done计数器
  while (done < nthread);        // 等待所有线程完成插入阶段

  t0 = now();                   // 记录查找阶段开始时间
  for (i = 0; i < NKEYS; i++) { // 查找阶段
    struct entry *e = get(keys[i]); // 查找键
    if (e == 0) k++;            // 如果未找到，增加缺失键计数器
  }
  t1 = now();                   // 记录查找阶段结束时间
  printf("%ld: get time = %f\n", n, t1 - t0); // 打印查找时间
  printf("%ld: %d keys missing\n", n, k); // 打印缺失键数量
  return NULL;                  // 线程返回
}

int main(int argc, char *argv[]) { // 主函数
  pthread_t *tha;                // 线程数组
  void *value;                   // 线程返回值
  long i;                        // 循环变量
  double t1, t0;                 // 时间变量

  if (argc < 2) {                // 检查参数数量
    fprintf(stderr, "%s: %s nthread\n", argv[0], argv[0]); // 打印用法
    exit(-1);                    // 退出程序
  }
  nthread = atoi(argv[1]);       // 设置线程数量
  tha = malloc(sizeof(pthread_t) * nthread); // 分配线程数组内存
  srandom(0);                    // 初始化随机数种子
  assert(NKEYS % nthread == 0);  // 检查NKEYS是否能被nthread整除
  for (i = 0; i < NKEYS; i++) {  // 生成随机键
    keys[i] = random();          // 存储随机键
  }
  t0 = now();                    // 记录程序开始时间
  pthread_mutex_init(&lock, NULL);
  for (i = 0; i < nthread; i++) { // 创建线程
    assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0); // 创建线程
  }
  for (i = 0; i < nthread; i++) { // 等待线程完成
    assert(pthread_join(tha[i], &value) == 0); // 等待线程结束
  }
  t1 = now();                    // 记录程序结束时间
  printf("completion time = %f\n", t1 - t0); // 打印总完成时间
}